package com.jml.排序;

import java.util.Arrays;

//左边排好序，右边排好序，进行总排序---使用递归
public class 归并排序test {


	public static void main(String[] args) {
		System.out.println("-----------------------------");
		int arr1[]={7,2,6,3,8,9};
		myselfMergeSort(arr1);
		for (int i : arr1){
			System.out.print(i+"-");
		}
	}

	private static void myselfMergeSort(int[] arr) {
		if(arr==null || arr.length<2){
			return;
		}

		myselfMergeSort(arr,0,arr.length-1);
	}
	private static void myselfMergeSort(int[] arr, int left, int right) {
		if(left==right){
			return;
		}
		int mid = (right+left)/2;
		myselfMergeSort(arr,left,mid);
		myselfMergeSort(arr,mid+1,right);
		myselfMerge(arr,left,right,mid);
	}
	private static void myselfMerge(int[] arr, int left, int right, int mid) {
		int[] help = new int[right-left+1];
		int i = 0;
		//左侧部分最小
		int p1 = left;
		//右侧部分最小
		int p2 = mid + 1;

		while (p1<=mid&&p2<=right){
			if(arr[p1]<arr[p2]){
				help[i]=arr[p1];
				p1++;
			}else{
				help[i]=arr[p2];
				p2++;
			}
			i++;
		}

		while(p1<=mid){
			help[i]=arr[p1];
			p1++;
			i++;
		}
		while(p2<=right){
			help[i]=arr[p2];
			p2++;
			i++;
		}
		for (int j = 0; j < help.length; j++) {
			arr[left+j] = help[j];
		}
	}

}
